package com.om39a.ds;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

/**
 * @author om39a
 * 
 *         Quick sort using recursion and two separate lists
 * 
 */
public class QuickSortMultiList {

	public static void main(String[] args) {
		Integer[] val = { 6, 4, 3, 2, 7, 9, 5, 1, 0, 8 };
		List<Integer> toSort = Arrays.asList(val);
		QuickSortMultiList quickSortMultiList = new QuickSortMultiList();
		System.out.println(quickSortMultiList.quickSort(toSort));
	}

	private List<Integer> quickSort(List<Integer> toSort) {
		if (toSort.size() <= 1) {
			return toSort;
		} else {
			List<Integer> leftList = new ArrayList<Integer>();
			List<Integer> rightList = new ArrayList<Integer>();
			List<Integer> mergedList = new ArrayList<Integer>();
			int pivotElement = toSort.get(toSort.size() - 1);
			for (int i = 0; i <= (toSort.size() - 2); i++) {
				if (toSort.get(i) < pivotElement) {
					leftList.add(toSort.get(i));
				} else if (toSort.get(i) > pivotElement) {
					rightList.add(toSort.get(i));
				}
			}
			leftList = quickSort(leftList);
			rightList = quickSort(rightList);
			mergedList.addAll(leftList);
			mergedList.add(pivotElement);
			mergedList.addAll(rightList);
			return mergedList;
		}
	}

}
